package sortAlgorithm;

import java.util.Arrays;

public class HeapSort {
	public static void main(String[] args) {
		int[] a = {8,5,10,7,4,9,7,2,23};
		heapSortDown(a);
		System.out.println(Arrays.toString(a));
		heapSortUp(a);
		System.out.println(Arrays.toString(a));
	}
	/***
	 * 由小到大
	 * @param array 待排数组
	 */
	public static void heapSortUp(int[] array) {
		makeMaxHeap(array);
		for(int i = array.length-1;i>=0;i--) {
			int temp = array[i];
			array[i] = array[0];
			array[0] = temp;
			maxHeapFixDown(array,0,i);
		}
	}
	/***
	 * 由大到小
	 * @param array 待排数组
	 */
	public static void heapSortDown(int[] array) {
		makeMinHeap(array);
		for(int i = array.length-1;i>=0;i--) {
			int temp = array[i];
			array[i] = array[0];
			array[0] = temp;
			minHeapFixDown(array,0,i);
		}
	}
	/**
	 * 堆化为小顶堆
	 * @param array	待堆化数组
	 */
	private static void makeMinHeap(int[] array) {
		for (int i = array.length / 2; i >= 0; i--) {
			minHeapFixDown(array, i, array.length);
		}
	}
	/**
	 * 堆化为大顶堆
	 * @param array	待堆化数组
	 */
	private static void makeMaxHeap(int[] array) {
		for(int i = array.length/2;i>=0;i--) {
			maxHeapFixDown(array, i, array.length);
		}
	}
	/**
	 * 调整为小顶堆
	 * @param array	待堆化数组
	 * @param i	要堆化二叉树最上层节点下标
	 * @param length	堆化的末元素下标或数组长度
	 */
	private static void minHeapFixDown(int[] array, int i, int length) {
		int j = 2 * i + 1;
		int temp = array[i];
		while(j<length) {
			if (j + 1 < length && array[j + 1] < array[j]) {
				j++;
			}
			if(array[j]<temp) {
				array[i] = array[j];
				i = j;
				j = 2*i+1;
			}else {
				break;
			}

		}
		array[i] = temp;
	}
	/**
	 * 调节为大顶堆
	 * @param array	待堆化数组
	 * @param i	要堆化二叉树最上层节点下标
	 * @param length	堆化的末元素下标或数组长度
	 */
	private static void maxHeapFixDown(int[] array,int i,int length) {
		int j = 2*i+1;
		int temp = array[i];
		while(j<length) {
			if(j+1<length&&array[j+1]>array[j]) {
				j++;
			}
			if(array[j]>temp) {
				array[i] = array[j];
				i = j;
				j = 2*i+1;
			}else {
				break;
			}
		}
		array[i] = temp;
	}
}
